import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item> {

    private int size;
    private Node head = new Node();
    private Node tail = new Node();

    private class Node {
        private Item item;
        private Node next;
        private Node previous;

        @Override
        public String toString() {
            return "Node [item=" + item + "]";
        }
    }

    private class DequeIterator implements Iterator<Item> {

        private Node current = head.next;

        @Override
        public boolean hasNext() {
            return !current.equals(tail);
        }

        @Override
        public Item next() {
            if (current == null || current.equals(tail)) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

    }

    /**
	 * 
	 */
    public Deque() {
        head.next = tail;
        tail.previous = head;

    }

    /**
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * insert the item at the front
     * 
     * @param item
     */
    public void addFirst(Item item) {
        if (item == null) {
            throw new NullPointerException();
        }
        Node oldFirst = head.next;
        Node first = new Node();
        first.item = item;
        first.previous = head;
        first.next = oldFirst;
        oldFirst.previous = first;
        head.next = first;
        size++;
    }

    /**
     * insert the item at the end
     * 
     * @param item
     */
    public void addLast(Item item) {
        if (item == null) {
            throw new NullPointerException();
        }
        Node oldLast = tail.previous;
        Node last = new Node();
        last.item = item;
        last.next = tail;
        last.previous = oldLast;
        oldLast.next = last;
        tail.previous = last;
        size++;
    }

    /**
     * delete and return the item at the front
     * 
     * @return
     */
    public Item removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Node oldFirst = head.next;
        Node newFirst = oldFirst.next;
        head.next = newFirst;
        newFirst.previous = head;
        size--;
        return oldFirst.item;
    }

    /**
     * delete and return the item at the end
     * 
     * @return
     */
    public Item removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Node oldLast = tail.previous;
        Node newLast = oldLast.previous;
        newLast.next = tail;
        tail.previous = newLast;
        size--;

        return oldLast.item;

    }

    /*
     * return an iterator over items in order from front to end
     * 
     * @see java.lang.Iterable#iterator()
     */
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }
}
